package leetcode.code1035;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int maxUncrossedLines(int[] nums1, int[] nums2) {
		int m = nums1.length, n = nums2.length;
		int[][] dp = new int[m + 1][n + 1];
		for (int i = 1; i <= m; i++) {
			int n1 = nums1[i - 1];
			for (int j = 1; j <= n; j++) {
				int n2 = nums2[j - 1];
				int max = 0;
				if (n1 == n2) {
					max = dp[i - 1][j - 1] + 1;
				}
				max = Math.max(max, Math.max(dp[i - 1][j], dp[i][j - 1]));
				dp[i][j] = max;
			}
		}
		return dp[m][n];
	}

	@Override
	public void debug4() {
		H.compare(2, this.maxUncrossedLines(H.str2array3("[1,4,2]"), H.str2array3("[1,2,4]")));
		H.compare(3, this.maxUncrossedLines(H.str2array3("[2,5,1,2,5]"), H.str2array3("[10,5,2,1,5,2]")));
		H.compare(2, this.maxUncrossedLines(H.str2array3("[1,3,7,1,7,5]"), H.str2array3("[1,9,2,5,1]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
